package maxProfit;

public class Solution {
    public int maxProfit(int[] prices) {
        // 思路 动态规划
        // dp[i] 表示第i天之前的最小利润
        // 第i天能获得的最大利润就是prices[i]-dp[i-1];
        int []dp = new int[prices.length];
        dp[0] = prices[0];
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.min(dp[i-1],prices[i]);
            ans = Math.max(prices[i]-dp[i-1],ans);
        }
        return ans;
    }

    // 拆分整数n为k个整数和
}
